#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "dsTree.h"

///
/// \brief keySign::keySign
///
///
///
//unsigned long count = 0;

keySign::keySign()
{
    keyNum = 0;
    for(int t = 0; t < 20; t ++)
    {
        key[t] = '\0';
    }
    sign = 0;
    nextKey = NULL;
}

int keySign::addKey(char *k, int s)
{
    keySign* newKey = new keySign;
    strcpy(newKey->key, k);
    newKey->sign = s;
    newKey->nextKey = this->nextKey;
    this->nextKey = newKey;
    this->keyNum++;
    return 1;
}


int keySign::setKey(char *k, int s)
{
    keySign* tmpKeySign = this->nextKey;
    while(tmpKeySign != NULL)
    {
        if(strcmp(tmpKeySign->key, k) == 0)
        {
            tmpKeySign->sign = s;
        }
        //return 1;
        tmpKeySign = tmpKeySign->nextKey;
    }
    return 1;
}


///
/// \brief dsTree::dsTree
///
dsTree::dsTree()
{
    isNum = -1;
    for(int t = 0; t < 30; t ++)
    {
        key[t] = '\0';
    }
    dAttri = NULL;
    dAttriNum = 0;
    cAttri = NULL;
    head = NULL;
    //count = 0;
}


int dsTree::testTree(valueItem *testItem, char *result)
{
    dsTree* finalTree = this->head->deciItem(testItem);
    if(finalTree != NULL)
    {
        strcpy(result, finalTree->dAttri->value);
    }
    else
    {
        return 0;
    }
    return 1;
}


dsTree* dsTree::deciItem(valueItem *testItem)
{

    if(strcmp(this->key, "class") == 0)
    {
        return this;
    }

    int isValueExist = 0;

    keyValue* tmpKV = testItem->getKeyValue(this->key);
    if(isNum == 0)
    {
        for(int t = 0; t < dAttriNum; t ++)
        {
            if(strcmp((dAttri+t)->value, tmpKV->valueStr) == 0)
            {
                isValueExist = 1;
                //decreAttri* tmpCA = dAttri+t;
                return (dAttri+t)->nextNode->deciItem(testItem);
            }
        }
        if(isValueExist == 0)
        {
            std::srand(time(NULL));
            return (dAttri + rand()%dAttriNum)->nextNode->deciItem(testItem);
        }
    }
    else
    {
        if(tmpKV->valueInt > cAttri->value)
        {
            if(this->cAttri->bigNode != NULL)
                return this->cAttri->bigNode->deciItem(testItem);
            else
            {
                return this->cAttri->smallNode->deciItem(testItem);
            }
        }
        else
        {
            if(this->cAttri->smallNode != NULL)
                return this->cAttri->smallNode->deciItem(testItem);
            else
            {
                return this->cAttri->bigNode->deciItem(testItem);
            }
        }
    }

    return NULL;

}

int dsTree::creatTree(trainData *td)
{
    dataChosen* chData = new dataChosen(td);    //获取数据
    valueItem* tmpVI = chData->nextData->item;  //获取第一条数据
    keySign* newKeySign = new keySign;          //从数据中分离出key
    for(int t = 0; t < tmpVI->getKeyValueNum(); t ++)
    {
        //把key存在keySign中
        newKeySign->addKey((tmpVI->getItem())[t].key, 0);
    }
    newKeySign->setKey((char*)"class", 1);     //将结果标记为已读
    dsTree* newNode = new dsTree;
    this->head = newNode;
    newNode->setNode(chData, newKeySign);   //开始构建决策数
    return 1;

}

int dsTree::setNode(dataChosen *dc, keySign *ks)
{
    if(dc->nextData == NULL)      //在指定属性下没有该分类
        return 0;
    keySign* tmpKS = ks->nextKey;   //获取第一个键

    //count ++;
    //std::cout << count << std::endl;

    char* maxKey;       //最大信息增益键
    double maxGain;     //最大信息增益

    char* tmpKey;
    double tmpGain;

    int s = 0;
    int isFinished = 1;     //标记是否每个属性都已分类
    //提取未被分类的键
    while(tmpKS != NULL)
    {
        if(tmpKS->sign == 1)        //该键已被分类
        {
            tmpKS = tmpKS->nextKey;
            continue;
        }
        isFinished = 0;

        tmpKey = tmpKS->key;        //获取键
        tmpGain = dc->gain(tmpKey); //获取该键的信息增益

        //std::cout << "here" << std::endl;

        if(s == 0)      //将最大信息初始化为第一个键
        {
            maxGain = tmpGain;
            maxKey = tmpKey;
        }

        if(tmpGain > maxGain)
        {
            maxGain = tmpGain;
            maxKey = tmpKey;
        }

        tmpKS = tmpKS->nextKey;
        s = 1;

    }

    if(isFinished == 1)
    {
        maxKey = dc->nextData->item->getKeyValue((char*)"class")->key;
    }

    keyValue* tmpKV = dc->nextData->item->getKeyValue(maxKey);
    valueSelect* tmpVS;
    ks->setKey(maxKey, 1);

    //到达分类结尾
    if(isFinished == 1)
    {
        tmpVS = dc->getValueClass(maxKey);
        tmpVS = tmpVS->nextValue;
        char* tmpClassValue = tmpVS->value;
        int tmpClassNum = tmpVS->valueNum;
        tmpVS = tmpVS->nextValue;
        while(tmpVS != NULL)
        {
            if(tmpVS->classNum > tmpClassNum)
            {
                tmpClassNum = tmpVS->classNum;
                tmpClassValue = tmpVS->value;
            }
            tmpVS = tmpVS->nextValue;
        }
        strcpy(this->key, "class");
        this->isNum = 0;
        this->dAttriNum = 1;
        this->dAttri = new decreAttri;
        strcpy(this->dAttri->value, tmpClassValue);
        this->dAttri->nextNode = NULL;
        delete dc;
        return 1;

    }

    strcpy(this->key, maxKey);


    if(tmpKV->isNum == 0)       //离散的数据
    {
        this->isNum = 0;
        tmpVS = dc->getValueClass(maxKey);
        dAttriNum = tmpVS->valueNum;
        dAttri = new decreAttri[dAttriNum];
        tmpVS = tmpVS->nextValue;
        for(int t = 0; tmpVS != NULL; t ++, tmpVS = tmpVS->nextValue)
        {
            strcpy(dAttri[t].value, tmpVS->value);
            (dAttri+t)->nextNode = new dsTree;
            (dAttri+t)->nextNode->setNode(dc->getKeyValueItem(maxKey, tmpVS->value), ks);
        }
    }
    else if(tmpKV->isNum == 1)  //连续的数据
    {
        this->isNum = 1;
        cAttri = new continAttri;
        cAttri->value = dc->infoKeyContin(maxKey, 1);
        //cAttri->smallNode = new dsTree;
        //cAttri->bigNode = new dsTree;

        dataChosen* smallTree = dc->getKeyContin(maxKey, cAttri->value, -1);    /////////
        if(smallTree->nextData != NULL)
        {
            cAttri->smallNode = new dsTree;
            cAttri->smallNode->setNode(smallTree, ks);
        }
        else
        {
            cAttri->smallNode = NULL;
        }

        dataChosen* bigTree = dc->getKeyContin(maxKey, cAttri->value, 1);
        if(bigTree->nextData != NULL)
        {
            cAttri->bigNode = new dsTree;
            cAttri->bigNode->setNode(bigTree, ks);
        }
        else
        {
            cAttri->bigNode = NULL;
        }

        //cAttri->smallNode->setNode(dc->getKeyContin(maxKey, cAttri->value, -1), ks);
        //cAttri->bigNode->setNode(dc->getKeyContin(maxKey, cAttri->value, 1), ks);
    }

    if(strcmp("class", maxKey) != 0)
        ks->setKey(maxKey, 0);
    delete dc;
    return 1;

}
